package com.samxcode.leetcode;

/**
 * Given a linked list, reverse the preNodes of a linked list k at a time and return its modified list.
 * 
 * If the number of preNodes is not a multiple of k then left-out preNodes in the end should remain as it
 * is.
 * 
 * You may not alter the values in the preNodes, only preNodes itself may be changed.
 * 
 * Only constant memory is allowed.
 * 
 * @author Sam
 *
 */
public class ReverseNodes {

    public static void main(String[] args) {
        ListNode.printListNode(reverseKGroup(ListNode.generateListNode(12), 3));
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        ListNode preNode = new ListNode(0);
        int i = 0;
        preNode.next = head;
        head = preNode;
        ListNode startNode = head;
        ListNode curNode, firstNode;
        while (preNode != null && preNode.next != null) {
            i++;
            if (i == k) {
                preNode = startNode.next;
                firstNode = preNode;
                for (; i > 1; i--) {
                    curNode = preNode.next;
                    preNode.next = curNode.next;
                    curNode.next = firstNode;
                    firstNode = curNode;
                }
                startNode.next = firstNode;
                startNode = preNode;
            }
            preNode = preNode.next;
        }
        return head.next;
    }
}
